論理と集合から始める数学の基礎 読書会
https://m.media-amazon.com/images/P/B079YZSYKY.01._SCLZZZZZZZ_SX500_.jpg
テキスト
方針
第二部終わりまで読めたら最高
途中で止まっても気にしない。そのうち再開できるかも
じっくり足固めして行きつ戻りつする
読めるかなcFQ2f7LRuLYP.icon
まだまだハードルが高い
一週間で14ページ進んだぞ！(2022/12/9)
二ヶ月で35ページまで来たぞ！(2023/02/01)
目次を貼り付けておこうtakker.icon
第１部 論理と集合の基礎
第1章 集合(その1)
1.2 集合の書き表し方
集合の内包的記法における普遍集合の明示
この本においては、普遍集合は文脈中で宣言するとのこと $ \{x\in U |P(x)\}じゃなくて$ \{x|P(x)\}の形をとる
第3章で論じる述語の真理集合との対応を明確にするために、あえて普遍集合は文脈中で宣言するらしい(p.6) 実際は前を使うのが一般的であるとは言ってる
この段階だと、まだ意図がわからないtakker.icon
cFQ2f7LRuLYP.iconさんが読み進めてくれるだろうから、それまで待機
1.4 演習問題
これ初耳takker.icon
なんのことだか気になる
真理値の話について書いてるcFQ2f7LRuLYP.icon
論理演算子や恒真命題、矛盾命題など
true falseを計算しているだけですね。理解takker.icon
代数ってなんだろう？cFQ2f7LRuLYP.icon 数字と文字を使って数の性質や相互関係を研究する学問 (角川新類語辞典)
ふーむ
未知数を文字でおいて式展開するやつ、ってくらいの認識でいいと思うtakker.icon
2.5 演習問題
全称命題は$ \forall xP(x)、すなわち「$ Uのすべての要素$ xは条件$ P(x)をみたす」
つまり「述語$ P(x)の真理集合は$ Uである」
存在命題は$ \exist xP(x)、「$ Uのなかのある要素$ xは条件$ P(x)をみたす」
真理集合を使って表すなら、「述語$ P(x)の真理集合は空集合ではない」ということ 書いてあることよくわかんねぇ～cFQ2f7LRuLYP.icon
ので一回整理
これは「条件文の命題」を表す時に使う
今回新しい話
例:$ P(x) \to Q(x)
どの論理記号$ \lor,\land,\lnotも使えるtakker.icon
ってどこかでやったか
2. でも、条件文の命題「$ P(x)ならばQ(x)」と述語「$ P(x) \to Q(x)」には意味のズレがある
前者は命題なので「真偽」が決定できる
後者は述語なので自由変数$ xに値が入らないと「真偽」を決定できない
………？？？？takker.icon
条件文の命題「$ P(x)ならばQ(x)」にも自由変数$ xが入っているが……
どゆこと？
言葉足らずすまぬcFQ2f7LRuLYP.icon
あんまり良くわかってないのがまるわかり！
言及箇所を引いてきた
ところが，数学の文脈で P(x)ならば Q(x)といえば，多くの場合，「Uの要素が条件 P(x)をみたせば，それは条件 Q(x)をみたす」という主張を意味します.そして，この主張は命題であって，真か偽かが定まっています.(p.36)
このあと真理集合の話になるがcFQ2f7LRuLYP.iconの理解が追っついてない()
/vim-jp-emojis/esper.iconすると、「Uの要素が条件 P(x)をみたせば，それは条件 Q(x)をみたす=$ \forall x\in U(P(x)\to Q(x))だと思われるtakker.icon
これなら真偽が定まるので確かに命題である
たぶんこれcFQ2f7LRuLYP.icon
暗黙的に全称の…その…あれがついているということ
言語化の難〜
図書館で確認してきました。これであってます
というかこの次の文章に書いてあった
ありがとうございます！cFQ2f7LRuLYP.icon
総括するとなんと表現できるか……cFQ2f7LRuLYP.icon
過去の俺がメモを書いていた
なるほど、変数の値が定まっているかどうかなんだな
「$ P(x)ならばQ(x)」の場合、(暗黙のうちに)全称量化子$ \forall xが変数の値として定まっている 言い方は正しくないかも
数学ではなく日本語の問題であったtakker.icon
この行まで読んでるcFQ2f7LRuLYP.icon
第4章 集合(その2)
第5章 2変数以上の述語
第6章 述語と数学的論証
第２部 集合で表される構造
ここから問題だけ拾い食いするtakker.icon
有向グラフとの関係が初見で新鮮だったtakker.icon 思えばグラフってtoとfromで一つの辺を指定できるから、順序対の集合で捉えることもできるのか グラフを扱うアルゴリズムを書いてるとこの辺は肌感覚として感じるnishio.icon
コラム19 有向グラフと2項関係
任意の有限集合$ Vと$ E\subseteq V^2を満たす$ Eについて、$ (V,E)を有向グラフと呼ぶ
$ Eの元が、グラフの矢印を表している
直積集合(の部分集合)と二項関係は一対一対応が成り立つので、どっちで表現しても同じこと
8.4 演習問題
8.1 $ X=\{a,b,c,d\}とし、$ X上の二項関係$ Rを以下の行列で定める
$ \begin{array}{c|cccc}&a&b&c&d\\\hline a&1&0&0&1\\b&1&1&1&1\\c&1&0&1&0\\d&0&0&1&1\end{array}
1. $ Rを集合とみなし、要素を全て書き並べて表せ
$ \{(x,y)\in X^2|R(x,y)\}=\{(a,a),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,c),(d,c),(d,d)\}
https://scrapbox.io/files/65f17d2a74fbcc00259b67ed.svg
code:8.1.2.tikz(tex)
\begin{document}
\tikzset{
col/.style={above,font=\Large},
row/.style={left,font=\Large},
point/.style={circle,fill,inner sep=2pt},
}
\drawthick (0,4) -- ++(4+0.5,0); \drawthick (0,4) -- ++(0,-4-0.5); \pathcol (0,4)--++(1,0)node{$a$}--++(1,0)node{$b$}--++(1,0)node{$c$}--++(1,0)node{$d$}; \node row at (0,3) {$a$}; \node row at (0,2) {$b$}; \node row at (0,1) {$c$}; \node row at (0,0) {$d$}; \path (0,3) -- ++(1,0)nodepoint{} -- ++(3,0)nodepoint{}; \path (0,2) -- ++(1,0)nodepoint{} -- ++(1,0)nodepoint{} -- ++(1,0)nodepoint{} -- ++(1,0)nodepoint{}; \path (0,1) -- ++(1,0)nodepoint{} -- ++(2,0)nodepoint{}; \path (0,0) -- ++(3,0)nodepoint{} -- ++(1,0)nodepoint{}; \end{tikzpicture}
\end{document}
3. $ Rを有向グラフで表せ
https://scrapbox.io/files/65f8f53b4f7c1800256793a9.svg
code:8.1.3.tikz(tex)
\begin{document}
\tikzset{
recursive/.style={in=60,out=120,looseness=6},
recursive flip/.style={out=-60,in=-120,looseness=6},
every node/.style={font=\Large},
}
\def\l{4}
\node (a) at (0,\l) {$a$};
\node (b) at (\l,\l) {$b$};
\node (c) at (\l,0) {$c$};
\node (d) at (0,0) {$d$};
edge (d)
(b) edge (a)
edge (c)
edge (d)
(c) edge (a)
(d) edge (c)
\end{tikzpicture}
\end{document}
8.2 以下に示す$ \R上の2項関係のグラフの概形を示せ
1. $ R_1(x,y):\iff x\le 2y
直線で区切られた領域
2. $ R_2(x,y):\iff x^2-y=0
横に寝た放物線
3. $ R_3(x,y):\iff x^2-y^2=0
2直線
4. $ R_4(x,y):\iff\exist t\in\R.x=2\cos t\land y=\sin t
x方向に長径2, y方向に短径1の楕円
図を書くのめんどいのでパスtakker.icon
9.1 順序関係
どうして線形がつくのだろうかtakker.icon
線形代数の意味の線形ではなく「一列に並んでる」のニュアンスnishio.icon
なるほど～めっちゃ納得takker.icon
(これはテキストにない)任意のmagma$ (A,\le)が以下を満たすとき、$ (A,\le)を前順序集合と呼ぶ 1. 反射律$ \forall x\in A.x\le x 2. 推移律$ \forall x,y,z\in A. x\le y\land y\le z\implies x\le z 3. 反対称律$ \forall x,y\in A.x\le y\land y\le x\implies x=y 4. 完全律$ \forall x,y\in A.x\le y\lor y\le x これで全ての元を一列に並べられることが保証される
任意の順序集合$ (U_1,\le_1),(U_2,\le_2)にて、以下の条件を満たす写像$ \varphi:U_1\to U_2を順序同型写像と呼ぶ 1. $ \varphiは全単射
2. $ \forall u,u'\in U_1.(u\le_1 u'\iff\varphi(u)\le_2\varphi(u'))
これが順序「構造を維持する」条件に該当する
順序同型写像が存在するとき、両者は順序同型であるという 同じ形になる
例9.6 $ S:=\{a,b,c\},D_{70}:=\{x\in\Z|70\backslash x\}として、$ (2^S,\subseteq),(D_{70},\backslash)のHasse図を比較する
右が$ (2^S,\subseteq), 左が$ (D_{70},\backslash)
https://scrapbox.io/files/65fd1d6893df1f0024e0d4a7.svg https://scrapbox.io/files/65fd1d6e8b0c94002545a32c.svg
要素が違うだけで、つながり方は全く同じだとわかる
同型の図的理解takker.icon
実際に順序同型であることを示す
$ \phi:S\to\{2,5,7\};a\mapsto2,b\mapsto5,c\mapsto7
$ \varphi:2^S\ni A\mapsto\prod_{x\in A}\phi(x)\in D_{70}
とすれば、$ \varphiが順序同型写像の一つになるので、$ 2^S,D_{70}が順序同型だとわかる
証明
一対一対応なのは列挙すればわかる(略)
なお、$ \forall P.\prod_{x\in\varnothing} P(x)=1とした
同型を証明する
$ \forall A,B\in 2^S.
$ A\subseteq B
$ \iff\forall x\in A.x\in B
$ \iff\forall x\in\phi[A].x\in\phi[B]
$ \iff \varphi(A)\backslash\varphi(B)
展開はちょい端折ったtakker.icon
$ \phi[B] が$ \phi[A] を包んでいるので、$ \phi[B] の総積は$ \phi[A] の総積で割り切れる
また総積を分解すれば元に戻るので、逆も成り立つ
code:9.6.1.tikz(tex)
\usepackage{amssymb}
\begin{document}
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\coordinate (left) at ({-sqrt(3)},1);
\coordinate (right) at ({sqrt(3)},1);
\draw (o)
edge (c)
-- (abc);
\draw (o)
edge (ac)
edge (b)
-- (abc);
\end{tikzpicture}
\end{document}
code:9.6.2.tikz(tex)
\usepackage{amssymb}
\begin{document}
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\coordinate (left) at ({-sqrt(3)},1);
\coordinate (right) at ({sqrt(3)},1);
\draw (o)
edge (c)
-- (abc);
\draw (o)
edge (ac)
edge (b)
-- (abc);
\end{tikzpicture}
\end{document}
コラム21 構造と同型
$ \forall x,y\in U.(x\wedge y\in U)\land (x\vee y\in U)を満たす$ (U,\le)を束(lattice)と呼ぶ $ \wedgeは結び、$ \veeは交わりと呼ぶ ここまで解いてるtakker.icon
TODO：解き残しがあるので、そっちを先に片付ける
図書館に返却してしまったので、しばらく進まない予定
問題を書き写しているのはやっておこうと思う
有限な束には必ず最大元と最小元が存在する
例9.10
9.7 演習問題
9.1 8.4 演習問題の8.1の$ Rが$ X上の順序関係でないことを証明せよ
$ \begin{array}{c|cccc}&a&b&c&d\\\hline a&1&0&0&1\\b&1&1&1&1\\c&1&0&1&0\\d&0&0&1&1\end{array}
反射律は成り立つ
対角線上に1が並んでいる
推移律が成り立たない
$ a,d,cがcyclicになっていて、推移律が成立していない
https://scrapbox.io/files/65f914bee052640023dc12f7.svg
よって、8.1の$ Rは順序関係でない
code:9.1.tikz(tex)
\begin{document}
\tikzset{
recursive/.style={in=60,out=120,looseness=6},
recursive flip/.style={out=-60,in=-120,looseness=6},
every node/.style={font=\Large},
}
\def\l{4}
\node (a) at (0,\l) {$\bf a$};
\nodegray (b) at (\l,\l) {$b$}; \node (c) at (\l,0) {$\bf c$};
\node (d) at (0,0) {$\bf d$};
(b) edge (a)
edge (c)
edge (d)
\end{tikzpicture}
\end{document}
9.4
9.5
9.6
9.7
第11章 集合の要素の個数
これ以降は飛ばしていいと思うtakker.icon
目次だけ頭にいれて、必要な時に学び始めればいい
2022-12-06 11:56:04 第16章はやったほうがよさそう
13~15を飛ばしてもやれると思う
練習問題スタック
うわあああああ▂▅▇█▓▒░cFQ2f7LRuLYP.icon░▒▓█▇▅▂
取り組んでない問題がたまるのって、こわい！
スマホだと改行されちゃうのでうわああああ感が減る
それはそれとして自分のアイコンが四角いのでただの階段のような何かになってる
図書館で見てきたtakker.icon
410.12||Ka 13
予想より内容が豊富だった
例や問題演習もたくさんついている
ちょくちょく問題を勝手に作っていたが、最初からこれだけあるなら変に作らなくてもいいかな